package com.cat.DataStructure04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/search-suggestions-system/description/
 * @create 2025/11/26 16:50
 * @since JDK17
 */

public class Solution17 {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> list = new ArrayList<>();
        Arrays.sort(products, Comparator.comparing(a -> a));
        for (int i = 0, n = products.length; i < searchWord.length(); i++) {
            String prefix = searchWord.substring(0, i + 1);
            ArrayList<String> t = new ArrayList<>();
            for (int j = 0, k = 0; j < n && k < 3; j++) {
                if (products[j].startsWith(prefix)) {
                    k++;
                    t.add(products[j]);
                }
            }
            list.add(t);
        }

        return list;
    }
}
